package com.sheng.project.test.sort;

/**
 * 归并排序：分两步
 * 分：将一个数组分割成两个数组，然后迭代分割知道最小单元为止
 * 治：将两个数组的第一个元素进行比较，排序
 *
 * @author liusheng
 * @date 2022/08/19
 */
public class MergeSort {

    public static void merge(int[] ints, int left, int right, int[] tempArray) {
        if (left < right) {
            int mid = (left + right) / 2;
            //向左递归分解
            merge(ints, left, mid, tempArray);
            //向右递归分解
            merge(ints, mid + 1, right, tempArray);
            //合并排序
            sort(ints, left, mid, right, tempArray);
        }
    }

    public static void sort(int[] ints, int left, int mid, int right, int[] tempArray) {
        // 初始化左右有序子数组的初始索引
        int i = left;
        int j = mid + 1;
        // 表示临时数组tempArray的当前索引
        int index = 0;
        // 左右子数组都还有元素未进行排序的时候，对左右子数组进行比较然后放到临时数组tempArray中
        while (i <= mid && j <= right) {
            if (ints[i] <= ints[j]) {
                // 如果左子树的元素小余等于右子树的元素时
                tempArray[index++] = ints[i++];
            } else {
                tempArray[index++] = ints[j++];
            }
        }
        // 左右子数组其中一个已经空了，那么将另一个子数组的元素依次放入临时数组tempArray中
        while (i <= mid) {
            tempArray[index++] = ints[i++];
        }
        while (j <= right) {
            tempArray[index++] = ints[j++];
        }
        // 将临时数组tempArray中的元素移动到原数组的对应位置
        index = 0;
        //left为原数组对应位置的初始索引
        int tempLeft = left;
        while (tempLeft <= right) {
            ints[tempLeft++] = tempArray[index++];
        }
    }
}
